package unionfind;

/**
 * @Description
 * @Author zhout
 * @Date 2019/1/30 13:31
 **/
//第四版并查集
public class UnionFind4 implements UF{
    private int[] parent;
    private int[] rank; //rank[i] 表示以i为根的集合深度
    public UnionFind4(int size){
        parent = new int[size];
        rank = new int[size];
        for(int i = 0; i < size; i++){
            parent[i] = i;
            rank[i] = 1;
        }
    }

    @Override
    public int getSize() {
        return parent.length;
    }

    //查找过程，查找元素p所对应的集合编号
    //o(h)复杂度，h为树的高度
    private int find(int p){
        if(p < 0 || p >= parent.length){
            throw new IllegalArgumentException("p is not bound.");
        }

        while(p != parent[p]){
            p = parent[p];
        }
        return p;
    }


    //查看元素p和元素q是否在同一个集合
    //o(h)复杂度，h为树的高度
    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    //合并元素p和元素q所属的集合
    //o(h)复杂度，h为树的高度
    @Override
    public void unionElements(int p, int q) {
        int proot = find(p);
        int qroot = find(q);
        if(proot == qroot){
            return;
        }

        if(rank[proot] < rank[qroot]){
            parent[proot] = qroot;
        }else if(rank[qroot] < rank[proot]){
            parent[qroot] = proot;
        }else{
            parent[qroot] = proot;
            rank[proot] += 1;
        }

    }
}
